#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 10
// 完全二叉树由于编号的特殊性，可以用顺序存储结构进行存储
// 非根节点i的父节点是[i/2]
// 结点i的左孩子结点为2i，右孩子结点为2i + 1（当然需要考虑范围）

// 一般的二叉树亦可以用上述方法，只需要补全为完全二叉树即可。但是这样会造成许多空间浪费

// 链表存储当然是最好的方法。

typedef struct TreeNode *BinTree;

struct TreeNode
{
    int Data;
    BinTree left;
    BinTree right;
};

// 没儿子的地方可以用NULL

// 二叉树的递归遍历

// 1.先序遍历：根节点->左子树->右子树  可以用递推实现
void PreOrderTraversal(BinTree BT)
{
    if (BT != NULL)
    {
        printf("%d ", BT->Data);
        PreOrderTraversal(BT->left);
        PreOrderTraversal(BT->right);
    }
}

// 2.中序遍历： 左子树->根节点->右子树
void InOrderTraversal(BinTree BT)
{
    if (BT != NULL)
    {
        InOrderTraversal(BT->left);
        printf("%d ", BT->Data);
        InOrderTraversal(BT->right);
    }
}

// 3.后序遍历： 左子树->右子树->根节点
void PostOrderTraversal(BinTree BT)
{
    if (BT != NULL)
    {
        PostOrderTraversal(BT->left);
        PostOrderTraversal(BT->right);
        printf("%d ", BT->Data);
    }
}

// 二叉树的非递归遍历，以中序遍历为例
// 基本思路:使用栈

// 我们先来构建栈的一些基本操作
typedef BinTree ElementType;
typedef struct SNode *Stack;
struct SNode
{
    ElementType Data[MAXSIZE];
    int top;
};

void Push(Stack PtrS, ElementType item)
{
    if (PtrS->top == MAXSIZE - 1)
    {
        printf("栈满\n");
        return;
    }
    else
    {
        PtrS->Data[++PtrS->top] = item; // top初始化为-1
        return;
    }
}

ElementType Pop(Stack PtrS)
{
    if (PtrS->top == -1)
    {
        printf("栈空\n");
        return -1;
    }
    else
    {
        return PtrS->Data[PtrS->top--];
    }
}

Stack CreateStack(void)
{
    struct SNode p;
    p.top = -1;
    Stack PtrS = &p;
    return PtrS;
}

int IsEmpty(Stack PtrS)
{
    if (PtrS->top == -1)
        return 1;
    else
        return 0;
}
// 接下来开始正式的中序遍历非递归算法
/*思路如下：
      遇到一个节点，就把他压栈，并去遍历他的左子树
      当左子树遍历结束后，从栈顶弹出这个节点并访问它
      然后按其右指针再去遍历该节点的右子树
      */
void InOrderTraversal_Stack(BinTree BT)
{
    BinTree T = BT;
    Stack S = CreateStack();
    while (T || !IsEmpty(S))
    {
        while (T != NULL)
        {
            Push(S, T);
            T = T->left;
        }
        if (!IsEmpty(S))
        {
            T = Pop(S);
            printf("%d ", T->Data);
            T = T->right;
        }
    }
}

// 先序遍历可不可以也用堆栈的方法实现？of course!
void PreOrderTraversal_Stack(BinTree BT)
{
    BinTree T = BT;
    Stack S = CreateStack();
    while (T || !IsEmpty(S))
    {
        while (T)
        {
            Push(S, T);
            printf("%d ", T->Data);
            T = T->left;
        }
        if (!IsEmpty(S))
        {
            T = Pop(S);
            T = T->right;
        }
    }
}

// 后序遍历呢？当然一样可以！只是我们
void PostOrderTraversal_Stack(BinTree BT)
{
    BinTree T = BT;
    BinTree prev = NULL; // 记录上一个访问的结点
    Stack S = CreateStack();
    while (T || !IsEmpty(S))
    {
        while (T)
        {
            Push(S, T);
            T = T->left;
        }
        if (!IsEmpty(S))
        {
            T = Pop(S);
            if (T->right == NULL || T->right == prev)
            { // 若当前结点无右子树，或右子树已访问，则访问当前节点
                printf("%d ", T->Data);
                prev = T;
                T = NULL;
            }
            else
            { // 否则，该节点重新入栈，转向右子树
                Push(S, T);
                T = T->right;
            }
        }
    }
}
